package graph;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

/**
 * 贝尔曼福特算法
 * 支持负权图的最短路径算法
 * 算法时间复杂都为：O(nm)，其中 n、m 分别为点数、边数
 */
public class BellmanFordNormal {
    public static Map<Node<Integer>, Integer> bellmanFord(Graph<Integer> graph, Node<Integer> source) {
        if (graph.nodeMap.isEmpty()) {
            return Collections.emptyMap();
        }

        Map<Node<Integer>, Integer> distanceMap = new HashMap<>(graph.nodeMap.size());
        // 初始化源点距离
        distanceMap.put(source, 0);

        // 节点数量
        final int n = graph.nodeMap.size();
        // 外层遍历n-1次
        for (int i = 1; i < n; i++) {
            // 内层每次遍历所有边
            // 第i次遍历，表示从源点出发至少经过i条边（注意这里的i是从1开始），到达任意点的最短距离
            for (Edge<Integer> edge : graph.edges) {
                // distanceMap中不存在的key，表示不可达的点，距离返回Integer.MAX_VALUE即可
                Integer fromNodeDistance = distanceMap.getOrDefault(edge.from, Integer.MAX_VALUE);
                Integer toNodeDistance = distanceMap.getOrDefault(edge.to, Integer.MAX_VALUE);

                final int newDistance = fromNodeDistance + edge.weight;
                if (newDistance < toNodeDistance) {
                    // 找到了更短的路径
                    distanceMap.put(edge.to, newDistance);
                }
            }
        }

        // 进行第n次松弛，检查负权环
        for (Edge<Integer> edge : graph.edges) {
            Integer fromNodeDistance = distanceMap.getOrDefault(edge.from, Integer.MAX_VALUE);
            Integer toNodeDistance = distanceMap.getOrDefault(edge.to, Integer.MAX_VALUE);

            final int newDistance = fromNodeDistance + edge.weight;
            if (newDistance < toNodeDistance) {
                // 移除存在负权环上的点
                distanceMap.remove(edge.to);
            }
        }

        return distanceMap;
    }
}
